import random
# coding: utf-8
import unittest
from typing import List


def quicksort(nums: List[int]) -> List[int]:
    if len(nums) <= 1:
        return nums

    return quicksort([x for x in nums[1:] if x <= nums[0]]) + [nums[0]] + quicksort([x for x in nums[1:] if x > nums[0]])


class TestQuickSort(unittest.TestCase):
    def test_qs(self):
        nums = [5,3,4,2,1]
        sn = quicksort(nums)
        self.assertEqual(sn, [1,2,3,4,5])

